package Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _114_FlattenBinaryTreetoLinkedList {
    //wrong thinking:doesn't need to order them,just flat to linked list by preorder.
    /*List<Integer> vals;
    public void flatten(TreeNode root) {
        if(root==null) return;
        vals = new ArrayList<>();
        traversal(root);
        int[] res = new int[vals.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = vals.get(i);
        }
        Arrays.sort(res);
        TreeNode temp = root;
        root.left = null;
        for (int i = 1; i < res.length; i++) {
            TreeNode t = new TreeNode(res[i]);
            temp.right = t;
            temp = t;
        }
    }

    public void traversal(TreeNode root) {
        if (root != null) {
            vals.add(root.val);
            traversal(root.left);
            traversal(root.right);
        }
    }*/
    public void flatten(TreeNode root) {
        if(root==null) return;
        traversal(root);
    }

    public TreeNode traversal(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root;
        }else if (root.left != null) {
            TreeNode rNode = root.right;
            root.right = root.left;
            root.left = null;
            TreeNode leafNode = traversal(root.right);
            if (rNode != null) {
                leafNode.right = rNode;
                return traversal(rNode);
            } else {
                return leafNode;
            }
        } else {
                return traversal(root.right);
        }
    }
}
